//
//  main.cpp
//  LinkList
//
//  Created by chenyh on 2021/2/4.
//

#include <iostream>
#include "LinkList.hpp"
using namespace std;
/**
 设计一个算法求出单链表的倒数第 m 个结点，要求不得求出链表长度，不得 对链表进行逆转，如果找到这样的结点就返回它的地址，如果没有就返回 NULL。
 【分析】该题目要求求出单链表的倒数第 m 个结点，但又不能逆转单链表。我们知道 获取单链表顺数第 i 个结点的方式是:设置指针 p=head，从头指针开始循环执行 p=p->next， 一步一步往后移，直到第 i 个结点停止。这里我们可以把这种方法稍加改动，即再设置一 个指针 q，使指针 q 也沿着链表向后移动并且比指针 p 落后 m1 步，当 p 到达链表尾部时，
 ·20·
 q 刚好指向倒数第 m 个结点。

 */
ListNode<int> * earchNodeM(LinkList<int> *link,int m)
{
    //p初始化为链表第一个结点
    ListNode<int> *p = link->findNode(1);
    if (p != NULL && m > 0) {
        for (int i = 1; i < m; i++) { //移动p到第m个结点
            p = p->getNext();
            if (p == NULL) {
                cout<<"该链表没有倒数第m个结点"<<endl;
                return NULL;
            }
        }
    }
    //很666的操作
    //假如有6个数（123456789.10） 取倒数第三个数 8，则先用p指向第三个数位置3
    //让q指向链表头部后。让p从m开始 移动到尾部 总共移动 length-m个长度 而q指向length-m个长度 从而得出q的地址
    ListNode<int> *q = link->findNode(1);
    while (p->getNext() != NULL) {
        p=p->getNext();
        q=q->getNext();
    }
    return q;
    
}
/**
 【例 1-3】给定一个单链表，请设计程序判断该链表是否有环。
 解了单链表的结构定义，它的每一个存储结点(头结
 点和尾结点除外)在结构上只有一个前驱结点和一个后继结点，其头结点没有前驱并且尾 结点没有后继。
 单链表有环只能是指它末尾有 环，不会是在中部，因为如果那样的话就违背了单 链表只有一个后继结点的要求。所以，我们可以将 带环的单链表看成是一个单链表与一个循环链表的 组合。判断一个单链表是否有环最简便的方法就是
 追逐法。设置两个指针 p 和 q 指向链表的头结点，然后循环移动两个指针，p 指针每次移 动一个结点，即一步，q 指针每次移动两步，如果该单链表存在环，那么这两个指针总会 在某个位置相遇。如果链表无环，则 q 会率先指向 NULL。
 */
bool isCircleLink(ListNode<int> *head) {
    if (head == NULL) {
        return false;//如果头结点为null，返回false
    }
    ListNode<int> *p,*q; //设置跑步指针
    p = q = head;        //初始化指针为head
    while (q != NULL && q->getNext() != NULL) {
        p = p->getNext();   // p每移动一步
        q = q->getNext()->getNext();//q每次移动两步
        if (p == q) {
            break;;
        }
    }
    if (p==q && p != NULL) { //相遇且不为null,则有环
        return true;
    }
    return false;
}
/**
 【例 1-4】如果发现一个单链表有环，如何找出环的起始位置?
 要找出环的起始位置，就需要分析链 表的环的长度与链表长度之间有什么样的联系。如果确定了环的长度与链表长度的关系，
就能很轻松地计算头结点到环起始位置之间的链表长度，这样环的起始位置就呼之欲出了。
 
 我们回顾判断链表是否有环的算法运行过
 程，有快慢两个指针 p 和 q。p 每次走一步，q 每
 次走两步，q 的速度是 p 的两倍。假设链表的长度
 为 L，链表起点到环的起点的距离为 a，环长度为 r。同时假设快指针和慢指针在相遇的时候，慢指
 针在环内已经走了 X 步，总共走了 S 步，那么快指针总共就走了 2S 步(快指针速度是慢 指针的两倍)。再相遇的时候快指针一定已经走了 n 圈环形路线了，所以我们有
 2S  S  nr (1) 从(1)式可以得出 S=nr。S 是慢指针 p 所走过的总共的步数，它主要由两部分构成:
 链表起点到环的起点之间的距离 a 和指针 p 在环内走的步数。所以
 SaX
 
 (2)式得到了慢指针的行走步数与环的起始位置之间的关系式。根据题目的条件，对 式(2)进行一系列的数学变形，得到
 aX nr(n1)rr(n1)rLa (3)
 得出
 a = (n 1)r  L  a  X
 
 由于(n1)r+L–a 表示的是相遇点的位置，且 L–a 等于环长度 r，那么 L–a–X 表示相 遇点继续前进到达环起始位置的距离。所以式(4)体现的意思就是链表起点到环的起点的 长度 a 与快慢指针相遇点到环的起始位置的长度相等。这一结论就是我们解决这道题目的 理论基础。我们在让快慢指针相遇之后，将快指针重新指向链表头部，同时让快指针 q 的 速度变得与慢指针 p 相同，继续移动两个指针，每次移动一步，当两个指针相遇时的结点
 就是链表环的起始位置
 
 */

bool circleStart(ListNode<int> *head) {
    if (head == NULL) {
        return false;//如果头结点为null，返回false
    }
    ListNode<int> *p,*q; //设置跑步指针
    p = q = head;        //初始化指针为head
    while (q != NULL && q->getNext() != NULL) {
        p = p->getNext();   // p每移动一步
        q = q->getNext()->getNext();//q每次移动两步
        if (p == q) {
            break;;
        }
    }
    if (p==q && p != NULL) { //相遇且不为null,则有环
        
        p = head;
        while (p != q) {
            p = p->getNext();   //继续移动直至相遇
            q = q->getNext();
        }
        return p;//返回相遇结点即为环起始位置
    }
    
    return false;
}

/**
 【例 1-5】编写程序判断两个链表是否相交。
 根据单链表的性质，每个结点只有一个后继结点，那么如果两个链表相交， 则只能有如图 1-12 所示的情形。
 两个链表只要相交则它们的尾结点必定相同。我们可以利用这 个性质来判断两个链表是否相交。首先遍历链表 a，并将指针停留在链表 a 的尾结点。然 后用一个新的指针指向链表 b 的头结点，遍历链表 b，判断链表 a 和 b 的尾结点指针所指 的地址是否相同，如果相同则这两个链表相交，如果不同，则不相交。
 
 */

bool isCrossLink(ListNode<int> *headA,ListNode<int> *headB) {
    if (headA == NULL || headB == NULL) {
        return false;
    }
    ListNode<int> *p,*q;
    p = headA;
    q = headB;
    while (p->getNext() != NULL) {
        p = p->getNext();
    }
    while (q->getNext() != NULL) {
        q = q->getNext();
    }
    if (p == q) {
        return true;
    }
    return false;
}
    




int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    return 0;
}
